package LeetCode._02算法基础.day05滑动窗口;

import org.junit.Test;

import java.util.Arrays;

/**
 * @author 挚爱之夕
 * @date 2022 - 03 - 15 - 20:03
 * @Description 给定一个含有n个正整数的数组和一个正整数 target
 * 找出该数组中满足其和 ≥ target 的长度最小的连续子数组，并返回其长度。
 * 如果不存在符合条件的子数组，返回 0 。
 * @Version 中等
 */
public class _209长度最小的子数组 {
    static int target = 7;
    static int[] nums = {2,3,1,2,4,3};
    @Test
    public void solve(){
        int res = minSubArrayLen2(target, nums);
        System.out.println(res);
    }
    /*by me 枚举窗口*/
    public int minSubArrayLen(int target, int[] nums) {
        int sum;
        int minLen = 0;
        for(int L = 1; L <= nums.length; L++){
            sum = 0;
            for(int i = 0; i < L; i++){
                sum += nums[i];
            }
            if(sum >= target){
                minLen = L;
                return minLen;
            }
            for(int i = L; i < nums.length; i++){
                sum -= nums[i - L];
                sum += nums[i];
                if(sum >= target){
                    minLen = L;
                    return minLen;
                }
            }
        }
        return minLen;
    }
    /*官方思路*/

    //1.前缀和 + 二分查找 O(n*logn)
    //因为这道题保证了数组中每个元素都为正，所以前缀和一定是递增的，这一点保证了二分的正确性
    public int minSubArrayLen1(int s, int[] nums) {
        int n = nums.length;
        if (n == 0) {
            return 0;
        }
        int ans = Integer.MAX_VALUE;
        int[] sums = new int[n + 1];
        // 为了方便计算，令 size = n + 1
        // sums[0] = 0 意味着前 0 个元素的前缀和为 0
        // sums[1] = A[0] 前 1 个元素的前缀和为 A[0]
        // 以此类推
        for (int i = 1; i <= n; i++) {
            sums[i] = sums[i - 1] + nums[i - 1];
        }
        for (int i = 1; i <= n; i++) {
            int target = s + sums[i - 1];
            int bound = Arrays.binarySearch(sums, target);
            if (bound < 0) {
                bound = -bound - 1;
            }
            if (bound <= n) {
                ans = Math.min(ans, bound - (i - 1));
            }
        }
        return ans == Integer.MAX_VALUE ? 0 : ans;
    }

    //2.滑动窗口
    public int minSubArrayLen2(int target, int[] nums) {
        int n = nums.length;
        if (n == 0) {
            return 0;
        }
        int ans = Integer.MAX_VALUE;
        int start = 0, end = 0;
        int sum = 0;
        while (end < n) {
            sum += nums[end];
            while (start <= end && sum >= target) {
                ans = Math.min(ans, end - start + 1);
                sum -= nums[start];
                start++;
            }
            end++;
        }
        return ans == Integer.MAX_VALUE ? 0 : ans;
    }

}
